/**

This file is part of MaCI/GIMnet.

MaCI/GIMnet is free software: you can redistribute it and/or modify it 
under the terms of the GNU Lesser General Public License as published 
by the Free Software Foundation, either version 3 of the License, or 
(at your option) any later version.

MaCI/GIMnet is distributed in the hope that it will be useful, but WITHOUT 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
License for more details.

You should have received a copy of the GNU Lesser General Public 
License along with GIMnet. (See COPYING.LESSER) If not, see 
<http://www.gnu.org/licenses/>.

**/
// code by jph

#ifndef _NTREE_HPP_
#define _NTREE_HPP_

#include <string.h>

template <class type> class ntree {
  public:
    ntree<type>(void);    
    virtual ~ntree<type>(void);
    ntree<type>(int n,type a);        //node w/ key a and n children
    ntree<type>(const ntree<type>& a);
    int link(ntree<type> *a);         //links at first available child index and returns index
    void link(int i,ntree<type> *a);  //n.link(i,m) link m to n as i th child
    ntree<type>* root(void);          //returns pointer to root of all the way up from this
    bool idnext(int *n);              //this is n child of parent otherwise false
    bool apply(bool (*func)(type));    //applies func to all nodes while true
    void destroy(void);                //delete all subtrees of node from memory
    void destruct(void);              //to be explained!!!!
    ntree<type> operator= (ntree<type>& a); //equal
  type data;
  int ary;                            //how many children  
  ntree<type> *prev;                   //pointer to parent
  ntree<type> **next;                  //pointer[] to children
};
//constructors-------------------------------------------------------------
template <class type> ntree<type>::ntree(void) {next=NULL;};
template <class type> ntree<type>::~ntree(void) {if (next) delete[] next;};
template <class type> ntree<type>::ntree(int n,type a) {  
  data=a;
  ary=n;
  prev=NULL;
  next=new ntree<type>*[n];
  for (int c1=0;c1<ary;c1++)
    next[c1]=NULL;
};
template <class type> ntree<type>::ntree(const ntree<type>& a) {
  data=a.data; ary=a.ary;  prev=a.prev;
  next=new ntree<type>*[ary];  
  memcpy(next,a.next,sizeof(ntree<type>*)*a.ary);  
};
//member funcs-------------------------------------------------------------
template <class type> int ntree<type>::link(ntree<type> *a) {
  for (int c1=0;c1<ary;c1++)
    if (!next[c1]) {
      next[c1]=a;
      a->prev=this;
      return c1;
    }
  return -1;
};
template <class type> void ntree<type>::link(int i,ntree<type> *a) {
  next[i]=a; a->prev=this;};
template <class type> ntree<type>* ntree<type>::root(void) {
  ntree<type> *r=this;
  while (r->prev!=NULL) r=r->prev;
  return r;
};  
template <class type> bool ntree<type>::idnext(int *n) {
  ntree<type> *p=this->prev;
  if (p) {*n=0;
    while (p->next[*n]!=this) (*n)++;
    return true;
  } else return false;
};
template <class type> bool ntree<type>::apply(bool (*func)(type)) {
  bool b1=func(data);
  if (b1)
    for (int c1=0;c1<ary;c1++)
      if (next[c1]) next[c1]->apply(func);
  return b1;
};
template <class type> void ntree<type>::destroy(void) {//
  for (int c1=0;c1<ary;c1++)
    if (next[c1]) {next[c1]->destroy(); delete next[c1]; next[c1]=NULL;}
};
template <class type> void ntree<type>::destruct(void) {
  for (int c1=0;c1<ary;c1++)
    if (next[c1]) {
      delete next[c1]->data;
      next[c1]->destruct();      
      delete next[c1];
      next[c1]=NULL;
    }
};
template <class type> ntree<type> ntree<type>::operator= (ntree<type>& a) {
  int c1;
  ntree<type> b;  
  data=a.data;
  ary=a.ary;
  prev=a.prev;  
  if (next) delete[] next;
  next=new ntree<type>*[ary];  
  memcpy(next,a.next,sizeof(ntree<type>*)*a.ary);  
  b.data=a.data; b.ary=a.ary; b.prev=prev;
  b.next=new ntree<type>*[ary];
  memcpy(b.next,a.next,sizeof(ntree<type>*)*a.ary);
  return b;
};
/*template <class type> void array<type>::operator= (array<type>& a) {          
  if (data==a.data) return;
  if (data) {delete[] data;  delete[] size;}
  ndims=a.ndims; size=new int[ndims];
  numel=a.numel; data=new type[numel];
  memcpy(size,a.size,4*ndims);
  memcpy(data,a.data,sizeof(type)*numel);
};*/


//set union forest nodes------------------------------------------------------
template <class type> class sutree : public ntree<type> {
  public:
    sutree<type>(void);    
    sutree<type>(type a);
    sutree<type>* fset();                  //path compression
    void join(sutree<type>* a);            //link by rank (return something?)
  protected:
    void link(sutree<type>* a);            //link by rank (return something?)
    //do NOT use root() for a find-set op!
    //int ary; is used for rank, hence dont cout nodes
};
template <class type> sutree<type>::sutree(void) : ntree<type>() {};
template <class type> sutree<type>::sutree(type a) : ntree<type>(0,a) {
  this->prev=(ntree<type>*)this;
};
template <class type> sutree<type> *sutree<type>::fset() {  
  if (this!=this->prev)
    this->prev=(sutree<type>*) ((sutree<type>*)this->prev)->fset();
  return (sutree<type>*) this->prev;
}
template <class type> void sutree<type>::join(sutree<type> *a) {
  fset()->link(a->fset());
}
template <class type> void sutree<type>::link(sutree<type> *a) {
  if (a->ary==this->ary)
    this->ary++;
  if (a->ary< this->ary)
    a->prev=(ntree<type>*)this;
  else
    this->prev=(ntree<type>*)a;
};


template <class type> class linked : public ntree<type> {
  public:
    linked<type>(void);            //a default const is always a good idea    
    ~linked<type>(void);          //removes nodes from memory (delete before the pointers !)
    void append(type a);          //append to the end
    void prepend(type a);          //append to the end
    //int head(type &a);            //while (list.token(by ref)) { ... }
    int token(type &a);            //while (list.token(by ref)) { ... }
    //void reset(void) {next[2]=this;};  //resets tokenizer
    //void advance(void);            //exchanges curr with head element (using this data!) DOES ANYBODY NEED THIS?
    void remove(void);            //remove current node during tokenize        
    linked<type>& operator<=(type a) {append(a); return *this;} //link<=1<=2;
    linked<type>& operator>=(type& a) {token(a); return *this;} //link>=a>=b;
    //bool operator~(void) {return next[2]->next[0];} //use for tokenizer status
};
template <class type> linked<type>::linked(void) : ntree<type>() {
  //int c1;
  this->ary=3;
  this->prev=NULL;
  this->next=new ntree<type>*[3];
  this->next[0]=NULL; //-> head (first element)
  this->next[1]=this; //-> last element)
  this->next[2]=this; //-> current (for tokenizer)
};
template <class type> linked<type>::~linked<type>(void) {//most elegant destructor
  ntree<type> *n=this->next[1];
  while ((n=n->prev)) delete n->next[0];
};
template <class type> void linked<type>::append(type a) {
  ntree<type> *x=new ntree<type>(1,a);
  x->prev=this->next[1];        // appended has pred last
  this->next[1]->next[0]=x;     // last has success appended
  this->next[1]=x;              // list has appended as last
};
template <class type> void linked<type>::prepend(type a) {
  ntree<type> *x=new ntree<type>(1,a);
  x->prev=this;                 // appended has pred last
  //x->next[0]=this->next[0];
  if ((x->next[0]=this->next[0]))            // if list has head
    this->next[0]->prev=x;      // new node is pred of prev head
  else
    this->next[1]=x;            // new node is last
  this->next[0]=x;              // new node is head
};
template <class type> int linked<type>::token(type &odata) {
  this->next[2]=this->next[2]->next[0]; // this means to reset tokenizer:
  if (this->next[2]) {
    odata=this->next[2]->data;
    return 1;
  } else {
    this->next[2]=this;
    return 0;
  }
};
template <class type> void linked<type>::remove(void) {
  ntree<type> *x=this->next[2]->prev;
  if (x) {
    x->next[0]=this->next[2]->next[0];
    if (x=this->next[2]->next[0]) {
      x->prev=this->next[2]->prev;
      delete this->next[2];
      this->next[2]=x->prev;
    } else {
      this->next[1]=this->next[2]->prev;
      delete this->next[2];
      this->next[2]=this->next[1];
    }
  }
};

/*
//binary search tree nodes---------------------------------------------------
template <class comp,class type> class bstree : public ntree<type> {
  public:
    bstree<comp,type>(void);            //a default const is always a good idea
    bstree<comp,type>(comp k,type a);    //node with key k
    bstree<comp,type> *locmin(void);    //pointer to local min
    bstree<comp,type> *locmax(void);    //pointer to local max
    bstree<comp,type> *suc(int d);      //d? pointer to successor acc. key
    void insert(comp k,type a);          //insert node 2b constructed
    void insert(bstree<comp,type> *z);  //insert node
    bool inorder(bool (*func)(type));    //inorder apply func
    bstree<comp,type> *remove();        //unlink node from rest/node itself loses no data/call delete with return value
    comp key;
};
template <class comp,class type> bstree<comp,type>::bstree(void) : ntree<type>() {key=NULL;};
template <class comp,class type> bstree<comp,type>::bstree(comp k,type a) : ntree<type>(2,a) {key=k;};
template <class comp,class type> bstree<comp,type>* bstree<comp,type>::locmin(void) {
  bstree<comp,type> *x=this;
  while (x->next[0]) x=(bstree<comp,type>*)x->next[0];
  return x;
};
template <class comp,class type> bstree<comp,type>* bstree<comp,type>::locmax(void) {
  bstree<comp,type> *x=this;
  while (x->next[1]) x=(bstree<comp,type>*)x->next[1];
  return x;
};
template <class comp,class type> bstree<comp,type>* bstree<comp,type>::suc(int d) {
  bstree<comp,type> *x=this,*y;
  if (x->next[1]) return ((bstree<comp,type>*)x->next[1])->locmin();
  y=(bstree<comp,type>*)x->prev;
  while (y) {
    if (x!=(bstree<comp,type>*)y->next[1]) return y;
    x=(bstree<comp,type>*)y;
    y=(bstree<comp,type>*)y->prev; };
  return y;
};
template <class comp,class type> void bstree<comp,type>::insert(comp k,type a) {
  bstree<comp,type> *x=new bstree<comp,type>(k,a);
  insert(x);
};
template <class comp,class type> void bstree<comp,type>::insert(bstree<comp,type> *z) {
  bstree<comp,type> *x=this,*y;
  while (x->prev!=NULL) x=(bstree<comp,type>*)x->prev;  //root()
  while (x!=NULL) {y=x;
    if (z->key<x->key) x=(bstree<comp,type>*)x->next[0];
                  else x=(bstree<comp,type>*)x->next[1];};
  z->prev=(ntree<type>*)y;                              //y.link(z)
  if (z->key<y->key)   y->next[0]=(ntree<type>*)z;      //%
                  else y->next[1]=(ntree<type>*)z;
};
template <class comp,class type> bool bstree<comp,type>::inorder(bool (*func)(type)) {    
  if (next[0]) next[0]->apply(func);
  bool b1=func(data);
  if (next[1]) next[1]->apply(func);
  return b1;
};
template <class comp,class type> bstree<comp,type>* bstree<comp,type>::remove() {
  bool b0,b1,bp; //has problems!!!
  int bi,n;
  b0=next[0];  b1=next[1];
  bp=idnext(&n);
  if (b0&&b1) {
    bstree<comp,type> *x;
    x=((bstree<comp,type>*)next[1])->locmin();
    data=x->data;  key=x->key;    
    return x->remove();}
  else if (b0||b1) {
    if (b0) bi=0; else bi=1;
    if (bp) prev->next[n]=next[bi];
    next[bi]->prev=prev;
    return this;}
  else {
    if (bp) {prev->next[n]=NULL; return this;}
      else return NULL;
  }
};


//operators-------------------------------------------------------------------
//template <class type> ostream& operator<< (ostream& os,ntree<type>& a) {    
//  int c1;
//  if (a.next) {
//  os << "[node@" << &a << "] par:" << a.prev << " #:" << a.ary << " data="<< a.data << endl;
//  for (c1=0;c1<a.ary;c1++) cout << " \\-" << c1 << ": " << a.next[c1] << endl;
//  } else os << "[node] <empty>" << endl;
//  return os;
//};
//template <class type> ostream& operator<< (ostream& os,linked<type>& a) {
//  int cnt=0;
//  type d;  
//  cout << (ntree<type>)a;
//  os << "{@";
//  while (a.token(d)) os << "," << d;
//  os << "}" << endl;
//  return os;
//};


//graph constructors--------------------------------------------------------------
//template <class type> class graph {
//  public:
//    graph<type>(array<ntree<type>*> *nodes,array<unsigned int> *ary,array<unsigned int> *edges);
//};
//
//template <class type> graph<type>::graph(array<ntree<type>*> *nodes,array<unsigned int> *ary,array<unsigned int> *edges) {
//  int c1;
//  for (c1=0;c1<nodes->numel;c1++) {
//    
//  }
//};
*/
#endif
